
class Solution {
    //前缀积*后缀积
    public int[] productExceptSelf(int[] nums){
        int n = nums.length;
        // int sum = Arrays.stream(nums).sum();
        int[] ans = new int[n];
        int[] left = new int[n]; int[] right = new int[n];
        left[0] = right[n-1] = 1;  //初始化第一个位置

        for(int i = 1; i < n; i++) left[i] = left[i-1] * nums[i-1];
        for(int i = n - 2; i >= 0 ;i--) right[i] = right[i+1] * nums[i+1];

        for(int i = 0; i < n; i++) ans[i] = left[i] * right[i];

        return ans;
    }
}
